A typical data system may have multiple tiers of storage. Higher tier storage may include high performance disks and flash-based storage devices that provide faster access times and other benefits. Lower tier storage may include generic disks that are able to store data cheaply. Tiering storage generally enhances the efficiency of data systems. For example, not all files are accessed frequently. Files that are accessed frequently may be stored on higher tier storage to allow for quick access. Files that are accessed infrequently may be stored on lower tier storage for economic reasons. Deduplication may further enhance the efficiency of data systems. Deduplication generally involves storing only a single instance of data, or a segment of data. Since many files may share common data segments, performing deduplication on one or more tiers of storage may potentially result in substantial storage savings.
Files typically do not stay in the same tier for prolonged periods of time. Some files may lose importance, causing them to be moved (e.g., migrated) to a lower tier storage. Similarly, some files may gain importance, causing them to be moved to higher tier storage. Unfortunately, moving files, or data, between different tiers may take a long time and computing resources if it involves moving the whole file or data. In a deduplication storage system, files are stored in a form of deduplicated segments. A deduplicated segment may be referenced by multiple files. Typically, when a file is moved from a storage tier to another storage tier, segments of the file are identified via a file system of a source tier and moved to a target tier. When the same segments are referenced by multiple files that are to be moved, for each of the files referencing the segments, the process of identifying the segments and/or determining the deduplication of the segments may be repeatedly performed. Such a process tends to be slow and inefficient due to the degradation in locality over time caused by space reclamation processes.